package FPGrowth;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.text.DecimalFormat;
import java.util.*;

public class FPTree {
	// FP tree node
	public class FPTreeNode {// 1 cay gom node va con cua no
		public ItemPrefixSubtreeNode node = null;// gom 4 thanh phan: cha no,anh
													// em no
		// ten no: ItemID, support cua no
		public LinkedList<FPTreeNode> childs = null;// childs la mot list cac
													// node

		public FPTreeNode() {
			childs = new LinkedList<FPTreeNode>();
		}

		public FPTreeNode(ItemPrefixSubtreeNode newNode) {
			node = newNode;
			childs = new LinkedList<FPTreeNode>();
		}

		public void InsertTransaction(Short[] dataArray, int minSupport) {// insert
																			// transaction
																			// vao
																			// cay
			SortItems(dataArray);// sap xep cac item theo support cua
									// chung
			FPTreeNode startNode = rootNode;
			if (dataArray.length > 0)
				if (supportCountHash.get(dataArray[0]) >= minSupport)
																		
																		// indexList
					InsertItems(dataArray, startNode, 0, minSupport);
		}

		public void InsertItems(Short[] dataArray, FPTreeNode startNode,
				int indexList, int support) {

			boolean IsFound = false;
			int index = -1;
			for (int i = 0; i < startNode.childs.size(); i++) {// xem ptu insert
																// trong
																// transaction
																// co trung voi
																// con cua cay
																// hay ko
				if (dataArray[indexList] == startNode.childs.get(i).node.itemID) {
					IsFound = true;
					index = i;
					break;
				}
			}

			if (IsFound) {// neu trung tang support len 1
				FPTreeNode t = startNode.childs.get(index);
				t.node.support++;
				startNode.childs.set(index, t);
				indexList++; // tang indexList len 1 tuc xet tiep phan tu tiep
								// theo trong transaction
				if (indexList < dataArray.length
						&& supportCountHash.get(dataArray[indexList]) >= support) {
																				
					InsertItems(dataArray, t, indexList, support);// neu
																	// transaction
																	// van con
																	// phan tu
																	// thi
																	// insert
																	// tiep
				}
			} else {// neu item insert vao ko trung voi con cua startnode thi,
				ItemPrefixSubtreeNode t = new ItemPrefixSubtreeNode(
						dataArray[indexList], 1, startNode.node);// tao moi mot
																	// node co
																	// supp=1
																	// ,node anh
																	// em =null
				FPTreeNode insertNode = new FPTreeNode(t);// tao mot cay voi goc
															// la item vua
															// insert
				startNode.childs.addLast(insertNode);// sau do gan cay do vao
														// mot nhanh con cua
														// startNode

				// Link header Table and same value
				int indexHeader = findIndexHeaderTable(dataArray[indexList]);// tim
																				// trong
																				// bangheaderTableFinal
																				// xem
																				// co
																				// luu
																				// Item
																				// nay
																				// hay
																				// chua
				if (indexHeader != -1) {// neu luu roi
					HeaderTable header = headerTableFinal[indexHeader];// thi
																		// tim
																		// cai
																		// node
																		// do
																		// trong
																		// headerTable
					// First item of type
					if (header.nodeLink == null) {// neu Item do ko co anh em
						header.nodeLink = insertNode.node;// sau do gan anh em
															// cua no vao
					} else {// neu da co anh em roi thi
						ItemPrefixSubtreeNode ref = header.nodeLink;
						while (ref.refSameItem != null) {
							ref = ref.refSameItem;
						}// lap cho den thang anh em cuoi
						ref.refSameItem = insertNode.node;// sau do gan thanh em
															// ut nay vao
					}
				}

				indexList++;
				if (indexList < dataArray.length
						&& supportCountHash.get(dataArray[indexList]) >= support) {// neu
																					// item
																					// do
																					// co
																					// support
																					// >=
																					// minsup
																					// thi
																					// moi
																					// insert
																					// vao
																					// tree
					InsertItems(dataArray, insertNode, indexList, support);

				}
			}
		}
	}

	public int findIndexHeaderTable(Short item) {
	
		for (int i = 0; i < headerTableFinal.length; i++) {
			if (headerTableFinal[i].itemID == item)
				return i;
		}
		return -1;
	}

	public void SortItems(Short[] dataArray2) {
		Arrays.parallelSort(dataArray2, new Comparator<Short>() {
			@Override
			public int compare(Short o1, Short o2) {
				int value = supportCountHash.get(o2) - supportCountHash.get(o1);
				if (value != 0)
					return value;
				else
					return o1 - o2;
			}
		});
	}

	// header table
	public class HeaderTable {
		protected short itemID;
		private int supportCount;
		private ItemPrefixSubtreeNode nodeLink = null;

		public HeaderTable(short colNum, int support) {
			supportCount = support;
			itemID = colNum;
		}

		public int getSupportCount() {
			return supportCount;
		}

		public short getItemID() {
			return itemID;
		}
	}

	public void CompleteHeaderTable() {
		boolean swapped = true;
		int j = 0;
		HeaderTable tmp;
		// Update support
		for (int i = 0; i < headerTable.size(); i++) {// cap nhat lai supp cho
														// cac item trong
														// hederTable
			tmp = headerTable.get(i);
			tmp.supportCount = supportCountHash.get(tmp.itemID);
			headerTable.set(i, tmp);
		}

		for (int i = 0; i < headerTable.size(); i++) {// neu headerTable nao <
														// minsup thi remove no
														// di
			if (headerTable.get(i).supportCount < minSupport) {
				headerTable.remove(i);
				i--;// do khi remove no ma ko giam i xuong se co headerTable ke
					// tiep ko duoc xet den
			}
		}
		// parallel sort
		headerTableFinal = headerTable.toArray(new HeaderTable[headerTable
				.size()]);// tao mot mang cac headerTable theo thuw tu support
		Arrays.parallelSort(headerTableFinal, new Comparator<HeaderTable>() {
			@Override
			public int compare(HeaderTable o1, HeaderTable o2) {
				int value = o2.getSupportCount() - o1.getSupportCount();
				if (value != 0)
					return value;
				else
					return o1.getItemID() - o2.getItemID();
			}

		});

		// headerTableFinal
	}

	// Item prefix subtree node
	public class ItemPrefixSubtreeNode {
		public short itemID;
		public int support;
		private ItemPrefixSubtreeNode parent = null;
		private ItemPrefixSubtreeNode refSameItem = null;

		public ItemPrefixSubtreeNode() {

		}

		public ItemPrefixSubtreeNode(short name, int itemCount,
				ItemPrefixSubtreeNode backRef) {
			itemID = name;
			support = itemCount;
			parent = backRef;
		}

		public ItemPrefixSubtreeNode(short name, int itemCount) {
			itemID = name;
			support = itemCount;
			parent = null;
		}
	}

	// update support hash
	public void updateSupportCountHash(short item) {
		if (supportCountHash.containsKey(item)) {// neu trong hash co Item nay
													// thi
			supportCountHash.put(item, supportCountHash.get(item) + 1);// tang
																		// support
																		// nay
																		// len 1
		} else {// con neu ko co thi
			supportCountHash.put(item, 1);// add vao hash Item voi support la 1
			// Add items to headerTable
			HeaderTable itemType = new HeaderTable(item, 0);
			headerTable.addLast(itemType);
		}

	}

	// get total rows in file
	public int getRows(File fileName) {
		int numRows = 0;
		File file = fileName;
		BufferedReader reader = null;

		try {
			reader = new BufferedReader(new FileReader(file));
			String line = reader.readLine();
			while (line != null) {
				numRows++;
				line = reader.readLine();
			}
			reader.close();
		} catch (Exception e) {

		}

		return numRows;
	}

	// read file to data array to reduce run time
	public void readFileToDataArray(File link) {
		// read input from file
		File file = link;
		BufferedReader reader = null;
		int numRows = getRows(link);
		dataArray = new Short[numRows][];

		try {
			reader = new BufferedReader(new FileReader(file));
			int rowIndex = 0;
			String current;
			current = reader.readLine();
			while (current != null) {
				StringTokenizer line = new StringTokenizer(current);
				dataArray[rowIndex] = new Short[line.countTokens()];
				int colIndex = 0;
				while (line.hasMoreElements()) {
					dataArray[rowIndex][colIndex] = Short.parseShort(line
							.nextElement().toString());
					colIndex++;
				}
				rowIndex++;
				current = reader.readLine();
			}
			reader.close();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	public FPTree() {
		rootNode = new FPTreeNode();
		headerTable = new LinkedList<HeaderTable>();
		minSupport = 0;
		minThreshold = 0;
		supportCountHash = new HashMap();
	}

	public FPTree(int minSup, int minThresh) {
		rootNode = new FPTreeNode();
		headerTable = new LinkedList<HeaderTable>();
		minSupport = minSup;
		minThreshold = minThresh;
		supportCountHash = new HashMap();

		
	}

	// fp tree root
	public FPTreeNode rootNode;
	// minimum support
	protected int minSupport;
	// minimum threshold
	protected int minThreshold;
	// protected CondPatBase listCPB = new CondPatBase();
	protected LinkedList<CondPattern> listParent = null;
	// header table
	protected LinkedList<HeaderTable> headerTable = null;
	// support count hash
	protected HeaderTable[] headerTableFinal;
	protected HashMap<Short, Integer> supportCountHash;
	// data array to store input data read from file
	protected Short[][] dataArray = null;

	protected LinkedList<CondPatternBase> cpbTable = new LinkedList<CondPatternBase>();
	protected LinkedList<SetAssRules> SetAssociationRules = new LinkedList<SetAssRules>();

	public class CondPattern extends Pattern {// mot list cac parent cua Item
												// tron headerTableFinal
		// vd: I5: items = I2, I1; suport = 0

		public CondPattern() {
			items = new LinkedList<ItemPrefixSubtreeNode>();
			support = 0;
		}

		public void insertPrefix(ItemPrefixSubtreeNode node) {
			ItemPrefixSubtreeNode nodetmp = node;
			while (nodetmp != null) {
				if (nodetmp.parent != null) {
					ItemPrefixSubtreeNode tmp = nodetmp.parent;
					if (tmp != null) {
						items.addFirst(tmp);
					}
				}
				nodetmp = nodetmp.parent;
			}
		}
	}

	public class CondPatternBase {// List cac bo cha cua anh em Item
		protected short itemID; // ten cua Item
		LinkedList<CondPattern> prefixList;// list cac cha cua no va anh em no

		public CondPatternBase() {
			prefixList = new LinkedList<CondPattern>();
		}

		public CondPatternBase(ItemPrefixSubtreeNode node) {
			itemID = node.itemID;
			prefixList = new LinkedList<CondPattern>();
		}

		public void insertCondPatternBase(ItemPrefixSubtreeNode node) {
			ItemPrefixSubtreeNode tmp = node;
			while (tmp != null) {
				CondPattern nodetmp = new CondPattern();
				nodetmp.insertPrefix(tmp);
				nodetmp.support = tmp.support;// update lai support cho List
												// parent = support cua Item
												// trong headerTable
				if (!nodetmp.items.isEmpty()) {// neu nodetmp co list cha khac
												// rong thi add vao list tong
												// hop cac cha cua anh em Item
												// do
					prefixList.add(nodetmp);
				}
				tmp = tmp.refSameItem; // duyet tiep toi anh em cua no den khi
										// nao het thi thoi
			}
		}

	}

	

	public CondPatternBase generateCondPatternBase(HeaderTable item) {// sinh
																		// ra,
																		// tao
																		// ra
																		// CondPatternBase
																		// voi
																		// item
																		// trong
																		// bang
																		// headerTable
		CondPatternBase condPattern = null;

		if (item.nodeLink != null) {
			condPattern = new CondPatternBase();
			condPattern.insertCondPatternBase(item.nodeLink);
			condPattern.itemID = item.itemID;
		}

		return condPattern;
	}

	public boolean containSinglePath() {// kt tra xem cay hien thoi co phai
										// duong di don hay ko?
		FPTreeNode tmpNode = rootNode;
		boolean flag = true;

		while (!tmpNode.childs.isEmpty()) {
			if (tmpNode.childs.size() > 1) {
				flag = false;
				break;
			}
			tmpNode = tmpNode.childs.get(0);
		}
		return flag;
	}

	public void miningFrequentPattern() {
		long start = System.currentTimeMillis();
		fpGrowth(this, null);
		long end = System.currentTimeMillis();
		System.out.println("time of mining frequent pattern: " + (end - start));

		start = System.currentTimeMillis();
		writeFrequentPatternToFile();
		end = System.currentTimeMillis();
		System.out.println("time of write down frequent pattern: "
				+ (end - start));

	}

	public int minSupBeta(LinkedList<ItemPrefixSubtreeNode> beta) {
		int min = beta.get(0).support;
		for (int i = 1; i < beta.size(); i++) {
			if (beta.get(i).support < min) {
				min = beta.get(i).support;
			}
		}
		return min;
	}

	public void fpGrowth(FPTree tree, LinkedList<ItemPrefixSubtreeNode> alpha) {
		if (tree.containSinglePath()) {// neu cay la duong di don thi
			LinkedList<LinkedList<ItemPrefixSubtreeNode>> combineNodeList = combineNodeInPath(tree.rootNode);

			for (LinkedList<ItemPrefixSubtreeNode> beta : combineNodeList) {
				Pattern pattern = new Pattern();
				pattern.items = generatePartern(beta, alpha);
				pattern.support = minSupBeta(beta);
				frequentPatterns.add(pattern);
			}
		} else {
			for (HeaderTable item : tree.headerTableFinal) {
				ItemPrefixSubtreeNode node = new ItemPrefixSubtreeNode(
						item.itemID, item.supportCount);
				LinkedList<ItemPrefixSubtreeNode> listA = new LinkedList<ItemPrefixSubtreeNode>();
				listA.add(node);

				Pattern pattern = new Pattern();
				pattern.items = generatePartern(listA, alpha);
				pattern.support = item.supportCount;
				frequentPatterns.add(pattern);

				CondPatternBase betaCondPatternBase = tree
						.generateCondPatternBase(item);

				FPTree treeBeta = new FPTree(minSupport, minThreshold);
				if (betaCondPatternBase != null) {
					treeBeta.generateFromCondPatternBase(betaCondPatternBase);
				}
				if (!treeBeta.isNull()) {
					fpGrowth(treeBeta, pattern.items);
				}
			}
		}
	}

	public class Pattern {
		protected LinkedList<ItemPrefixSubtreeNode> items;
		protected int support;

		public Pattern() {
			items = new LinkedList<ItemPrefixSubtreeNode>();
			support = 0;
		}
	}

	protected LinkedList<Pattern> frequentPatterns = new LinkedList<FPTree.Pattern>();

	// frequentPatterns la table Frequent Patterns Generated
	public LinkedList<LinkedList<ItemPrefixSubtreeNode>> combineNodeInPath(
			FPTreeNode root) {
		Pattern partern = new Pattern();
		FPTreeNode tmp = root;

		while (!tmp.childs.isEmpty()) {
			partern.items.add(tmp.childs.get(0).node);
			tmp = tmp.childs.get(0);
		}

		LinkedList<LinkedList<ItemPrefixSubtreeNode>> result = getSubSetList(partern.items);
		result.removeLast();
		return result;
	}

	public LinkedList<LinkedList<ItemPrefixSubtreeNode>> getSubSetList(
			LinkedList<ItemPrefixSubtreeNode> list) {
		LinkedList<LinkedList<ItemPrefixSubtreeNode>> result = new LinkedList<LinkedList<ItemPrefixSubtreeNode>>();

		if (list.isEmpty()) {
			result.add(new LinkedList<FPTree.ItemPrefixSubtreeNode>());
			return result;
		}

		ItemPrefixSubtreeNode head = list.remove(0);

		for (LinkedList<ItemPrefixSubtreeNode> subSet : getSubSetList(list)) {
			LinkedList<ItemPrefixSubtreeNode> tmp = new LinkedList<FPTree.ItemPrefixSubtreeNode>();
			tmp.add(head);
			tmp.addAll(subSet);
			result.add(tmp);
			result.add(subSet);
		}
		return result;
	}

	public LinkedList<ItemPrefixSubtreeNode> generatePartern(
			LinkedList<ItemPrefixSubtreeNode> list1,
			LinkedList<ItemPrefixSubtreeNode> list2) {
		if (list1 == null && list2 == null)
			return null;
		if (list1 != null && list2 == null)
			return list1;
		if (list2 != null && list1 == null)
			return list2;
		list1.addAll(list2);
		return list1;
	}

	public void generate(File link) {

		long start = System.currentTimeMillis();

		readFileToDataArray(link);
		// qua trinh update support cho cac item trong hash
		for (int i = 0; i < dataArray.length; i++) {
			for (int j = 0; j < dataArray[i].length; j++) {
				updateSupportCountHash(dataArray[i][j]);
			}
		}

		long end = System.currentTimeMillis();

		System.out.println("time of read file: " + (long) ((end - start)));

		start = System.currentTimeMillis();
		CompleteHeaderTable();
		end = System.currentTimeMillis();
		System.out.println("time of sort header table: "
				+ (long) ((end - start)));

		// add node to fp tree
		start = System.currentTimeMillis();

		for (int i = 0; i < dataArray.length; i++) {
			rootNode.InsertTransaction(dataArray[i], minSupport);
		}

		end = System.currentTimeMillis();
		System.out.println("time of fp generate: " + (long) ((end - start)));
		
	}

	public void generateFromCondPatternBase(CondPatternBase condPatternBase) {
		Short[][] data;
		int numRows = 0;
		int currentRow = 0;

		for (CondPattern prefix : condPatternBase.prefixList) {
			numRows += prefix.support;
		}

		data = new Short[numRows][];

		for (CondPattern prefix : condPatternBase.prefixList) {
			for (int time = 0; time < prefix.support; time++) {
				int currentCol = 0;
				data[currentRow] = new Short[prefix.items.size()];
				for (ItemPrefixSubtreeNode item : prefix.items) {
					data[currentRow][currentCol] = item.itemID;
					currentCol++;
				}

				currentRow++;
			}
		}
		
		generate(data);

	}

	public void generate(Short[][] data) {
		// read input from data array
		
		for (int i = 0; i < data.length; i++) {
			for (int j = 0; j < data[i].length; j++) {
				updateSupportCountHash(data[i][j]);
			}
		}

		// sort header table
		CompleteHeaderTable();

		// build fp tree with it's header table (headerTableFinal)
		for (int i = 0; i < data.length; i++) {
			rootNode.InsertTransaction(data[i], minSupport);
			
		}
	}

	public boolean isNull() {
		if (rootNode.childs.isEmpty())
			return true;
		return false;
	}

	public void writeFrequentPatternToFile() {
		try {
			StringBuilder content = new StringBuilder();

			File file = new File("freq_pattern.txt");

			if (!file.exists()) {
				file.createNewFile();
			}

			FileWriter fw = new FileWriter(file.getAbsoluteFile());
			BufferedWriter bw = new BufferedWriter(fw);

			for (Pattern pattern : frequentPatterns) {

				content.append("{");
				for (ItemPrefixSubtreeNode item : pattern.items) {
					content.append(Short.toString(item.itemID) + ", ");
				}
				content.append("sup: " + Integer.toString(pattern.support)
						+ "}");
				content.append("\n");
				if (content.length() > 1024) {
					String tmp = content.toString();
					content = new StringBuilder();
					bw.write(tmp);
				}
				
			}
			String tmp = content.toString();
			bw.write(tmp);
			bw.close();

			System.out.println("done");
		} catch (IOException e) {

		}

	}

	// lay listChildRight
	public class associationRules {
		protected LinkedList<ItemPrefixSubtreeNode> listItemLeft;
		protected LinkedList<ItemPrefixSubtreeNode> listItemRight;
		protected float confidence;

		public associationRules(LinkedList<ItemPrefixSubtreeNode> listParent,
				LinkedList<ItemPrefixSubtreeNode> listChildLeft,
				LinkedList<ItemPrefixSubtreeNode> listChildRight,
				int supportParent) {
			listItemLeft = listChildLeft;

			listItemRight = listChildRight;

			int numeratorConf = supportParent;
			int denominatorConf = 0;//
			if (!listChildLeft.isEmpty()) {
				if (listChildLeft.size() == 1) {
					denominatorConf = supportCountHash
							.get(listChildLeft.get(0).itemID);
					confidence = (float) numeratorConf / denominatorConf * 100;
				} else {
					for (int i = 0; i < frequentPatterns.size(); i++) {
						LinkedList<ItemPrefixSubtreeNode> tmpf = frequentPatterns
								.get(i).items;
						if (tmpf.size() == listChildLeft.size()) {
							boolean isTrue = true;
							for (int j = 0; j < listChildLeft.size(); j++) {
								if (checkInList(tmpf,
										listChildLeft.get(j).itemID) == false) {
									isTrue = false;
									break;
								}
							}
							if (isTrue == true) {// /
								denominatorConf += frequentPatterns.get(i).support;
							}
						}
					}
				}
			}
			DecimalFormat formater = new DecimalFormat("0.##");
			if (denominatorConf != 0){
				confidence = (float) numeratorConf / denominatorConf * 100;
				confidence=Float.parseFloat(formater.format(confidence));
			}

			// }
		}

		private boolean checkInList(LinkedList<ItemPrefixSubtreeNode> list,
				Short id) {
			for (int i = 0; i < list.size(); i++) {
				if (list.get(i).itemID == id)
					return true;
			}
			return false;
		}

		

	}

	// list cac luat cua 1 frequentPattern
	public class SetAssRules {
		LinkedList<associationRules> ListAssRule;

		public SetAssRules() {
			ListAssRule = new LinkedList<associationRules>();
		}

		public void insertSetAssRules(Pattern frePattern) {
			// list cha
			// Pattern tmpfrePttern = frePattern;
			// list con cua list cha
			LinkedList<LinkedList<ItemPrefixSubtreeNode>> listSub;

			LinkedList<ItemPrefixSubtreeNode> tmp = new LinkedList<ItemPrefixSubtreeNode>();

			for (int i = 0; i < frePattern.items.size(); i++) {
				ItemPrefixSubtreeNode t = frePattern.items.get(i);
				tmp.add(new ItemPrefixSubtreeNode(t.itemID, t.support));
			}

			listSub = getSubSetList(tmp);
			
			if (listSub.size() != 0) {

				for (int i = 0; i < listSub.size(); i++) {
					if (listSub.get(i).size() != 0
							&& listSub.get(i).size() != frePattern.items.size()) {
						LinkedList<ItemPrefixSubtreeNode> listChildLeft = listSub
								.get(i);
						LinkedList<ItemPrefixSubtreeNode> listChildRight = extant(
								frePattern.items, listChildLeft);
						associationRules assRules = new associationRules(
								frePattern.items, listChildLeft,
								listChildRight, frePattern.support);
								ListAssRule.add(assRules);
					}

				}
			}
		}
	}

	public void generate_SetAssociationRules() {
		SetAssRules tmpSetAssRules;
		long start = System.currentTimeMillis();
		for (int i = 0; i < frequentPatterns.size(); i++) {
			if (frequentPatterns.get(i) != null) {
				tmpSetAssRules = new SetAssRules();
				tmpSetAssRules.insertSetAssRules(frequentPatterns.get(i));
				SetAssociationRules.add(tmpSetAssRules);

			}
		}

		for (int i = 0; i < SetAssociationRules.size(); i++) {
			if (SetAssociationRules.size() != 0) {
				SetAssRules setAssRules = SetAssociationRules.get(i);
				LinkedList<associationRules> listAsRu = setAssRules.ListAssRule;
				for (int j = 0; j < listAsRu.size(); j++) {
					if (listAsRu.get(j).confidence < minThreshold) {
						listAsRu.remove(j);
						j--;
					}
				}
			}
		}

		long end = System.currentTimeMillis();
		System.out.println("time of SetAssociationRules: "
				+ (long) ((end - start)));
		
		
		writeAssociationRuleToFile();
	}

	public void writeAssociationRuleToFile() {
		try {
			String content = new String();

			File file = new File("assoc_rule.txt");

			if (!file.exists()) {
				file.createNewFile();
			}

			FileWriter fw = new FileWriter(file.getAbsoluteFile());
			BufferedWriter bw = new BufferedWriter(fw);

			for (SetAssRules tmp : SetAssociationRules) {// hien thi ket qua
				for (associationRules tmp1 : tmp.ListAssRule) {
					content+="{";
					for (int i =0; i< tmp1.listItemLeft.size(); i++){
						ItemPrefixSubtreeNode t = tmp1.listItemLeft.get(i);
						if (i== tmp1.listItemLeft.size()-1)
							content+=(t.itemID + " ");
						else
							content+=t.itemID + "^";
					}
					content+=" => ";
					for (int i =0; i< tmp1.listItemRight.size(); i++){
						ItemPrefixSubtreeNode t = tmp1.listItemRight.get(i);
						if (i== tmp1.listItemRight.size()-1)
							content+=t.itemID + " ";
						else
							content+=t.itemID + "^";
					}
					content+=(" " + tmp1.confidence + "}   ");
				}
				
				if(!content.equals("\n")){
					
					bw.write(content);
					content ="\n";
				}
				
			}
			
			
			bw.close();
			System.out.println("assoc write");
			System.out.println("done");
		} catch (IOException e) {

		}

	}

	public LinkedList<ItemPrefixSubtreeNode> extant(
			LinkedList<ItemPrefixSubtreeNode> listParent,
			LinkedList<ItemPrefixSubtreeNode> listChildLeft) {

		if (listParent == null && listChildLeft == null)
			return null;
		if (listParent != null && listChildLeft == null)
			return listParent;
		if (listChildLeft != null && listParent == null)
			return null;
		LinkedList<ItemPrefixSubtreeNode> listChildRight = new LinkedList<ItemPrefixSubtreeNode>();

		for (int j = 0; j < listParent.size(); j++) {
			boolean insert = true;
			for (int i = 0; i < listChildLeft.size(); i++) {
				if (listParent.get(j).itemID == listChildLeft.get(i).itemID) {
					insert = false;
				}
			}
			if (insert == true) {
				ItemPrefixSubtreeNode t = new ItemPrefixSubtreeNode(
						listParent.get(j).itemID, listParent.get(j).support);
				listChildRight.add(t);
			}
		}
		return listChildRight;
	}
}
